package com.hardy.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * User: Ruijie Date: 2016/9/8
 */
public class UniqueBinarySearchTreesLL {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public static ArrayList<TreeNode> generateTrees(int n) {
        ArrayList<TreeNode> result=new ArrayList<TreeNode>();
        if(n<=0){
            return result;
        }
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=i+1;
        }
        pailie(res,arr,0);
        Collections.sort(res, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                for(int i=0;i<o1.size();i++){
                    if(o1.get(i)>o2.get(i)){
                        return -1;
                    }else if (o1.get(i)<o2.get(i)){
                        return 1;
                    }else{
                        return 0;
                    }
                }
                return 0;
            }
        });
        for(ArrayList<Integer> a:res){
            TreeNode root=generateBST(a);
            boolean found=false;
            for(TreeNode at:result){
                if(isSameTree(root,at)){
                    found=true;
                    break;
                }
            }
            if(!found){
                result.add(root);
            }
        }
        return result;
    }

    public static TreeNode generateBST(ArrayList<Integer> a){
        TreeNode root=new TreeNode(a.get(0));
        for(int i=1;i<a.size();i++){
            TreeNode node=new TreeNode(a.get(i));
            //createNode(node,root);
            TreeNode p=root;
            TreeNode current=p;
            while(p!=null){
                if(p.val>node.val){
                    current=p;
                    p=p.left;
                }else{
                    current=p;
                    p=p.right;
                }
            }
            if(current.val>node.val){
                current.left=node;
            }else{
                current.right=node;
            }
        }
        return root;
    }


    public static void pailie(ArrayList<ArrayList<Integer>> res,int[] arr,int begin){
        if(begin==arr.length){
            ArrayList<Integer> item=new ArrayList<Integer>();
            for(int i:arr){
                item.add(i);
            }
            res.add(item);
        }
        for(int i=begin;i<arr.length;i++){
            swap(arr,begin,i);
            pailie(res,arr,begin+1);
            swap(arr,i,begin);
        }
    }

    private static void swap(int[] arr, int begin, int i) {
        int temp=arr[begin];
        arr[begin]=arr[i];
        arr[i]=temp;
    }

    public static boolean isSameTree(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null){
            return true;
        }
        if(root1==null||root2==null){
            return false;
        }
        if(root1.val!=root2.val){
            return false;
        }
        return isSameTree(root1.left,root2.left)&&isSameTree(root1.right,root2.right);
    }

    public static void printInOrderTree(TreeNode root){
        if(root!=null){
            printInOrderTree(root.left);
            System.out.print(root.val+" ");
            printInOrderTree(root.right);
        }
    }


    // for test -- print tree
    public static void printTree(TreeNode head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(TreeNode head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.val + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> res1=new ArrayList<ArrayList<Integer>>();
        int[] n={1,2,3};
        pailie(res1,n,0);
        System.out.println(res1);
        Collections.sort(res1, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                for(int i=0;i<o1.size();i++){
                    if(o1.get(i)!=o2.get(i)){
                        if(o1.get(i)>o2.get(i)){
                            return 1;
                        }else{
                            return -1;
                        }
                    }

                }
                return 0;
            }
        });
        System.out.println(res1);
        /*ArrayList<TreeNode> res=generateTrees(3);
        for(TreeNode node:res){
            printTree(node);
        }*/

    }
}
